// https://www.lintcode.com/problem/island-city/description

// 法一：UF
// class UnionFind {
//     public:
//         int* father;
//         bool* hasCity;
//         // int count; 初始化！
//         int count = 0;
//     UnionFind(vector<vector<int>> grid) {
//         int n = grid.size();
//         int m = grid[0].size();
//         father = new int[n * m];
//         hasCity = new bool[n * m];
//         for (int i = 0; i < n; ++i) 
//         {
//             for (int j = 0; j < m; ++j)
//             {
//                 father[i * m + j] = i * m + j;
//                 hasCity[i * m + j] = (grid[i][j] == 2);
//                 if (hasCity[i * m + j])
//                     count++;
//             }
//         }
//     }
//     int find(int n) {
//         if (father[n] == n) {
//             return n;
//         }
//         return find(father[n]);
//     }
//     void connect(int a, int b)  {
//         int rootA = find(a);
//         int rootB = find(b);
//         if (rootA != rootB) {
//             father[rootA] = rootB;
//             // if (hasCity[a] && hasCity[b])
//             if (hasCity[rootA] && hasCity[rootB])
//                 count--;
//             hasCity[rootA] = hasCity[rootA] || hasCity[rootB];
//             hasCity[rootB] = hasCity[rootA];
//         }
//     }
//     int check() {
//         return count;
//     }
// };
// class Solution {
// public:
//     /**
//      * @param grid: a boolean 2D matrix
//      * @return: an integer
//      */
     
//     // Union Find 解法，但是对于每块陆地，只需要检测其右面和下面是否是陆地然后做connect，不需要对左和上再作判断，因为遍历顺序是从上到下，从左到右。
//     int numIslandCities(vector<vector<int>> &grid) {
//         if (grid.empty() || grid[0].empty()) {
//             return 0;
//         }
//         int n = grid.size();
//         int m = grid[0].size();
        
//         UnionFind u(grid);
//         for (int i = 0; i < n; i++) {
//             for (int j = 0; j < m; j++) {
//                 if (grid[i][j]) {
//                     if (j + 1 < m && grid[i][j + 1]) {
//                         u.connect(i * m + j, i * m + j + 1);
//                     }
//                     if (i + 1 < n && grid[i + 1][j]) {
//                         u.connect(i * m + j, i * m + j + m);
//                     }
//                 }
//             }
//         }
//         return u.check();
//     }
// };



// 法二：BFS
// struct Node
// {
//     int x;
//     int y;
// };
// class Solution {
// public:
//     int numIslandCities(vector<vector<int>> &grid) {
//         if (grid.empty() || grid[0].empty()) {
//             return 0;
//         }
//         int dx[4] = {-1, 1, 0, 0}; 
//         int dy[4] = {0, 0, -1, 1};
//         int n = grid.size();
//         int m = grid[0].size();
//         queue<Node> q;
//         int cnt = 0;
//         bool hasCity;
//         for (int i = 0; i < n; ++i)
//         {
//             for (int j = 0; j < m; ++j)
//             {
//                 hasCity = false;
//                 if(grid[i][j])
//                 {
//                     if (grid[i][j] == 2) 
//                         hasCity = true;
//                     Node node = {i, j};
//                     q.push(node);
//                     // grid[i][j] == 0; //注意:赋值为0；别再出现写成==的情况了！
//                     grid[i][j] = 0; 
//                     while (!q.empty())
//                     {
//                         Node tmp = q.front();
//                         q.pop();
//                         for (int i = 0; i < 4; ++i)
//                         {
//                             int nx = tmp.x + dx[i];
//                             int ny = tmp.y + dy[i];
//                             // if (grid[nx][ny])
//                             // if (nx > 0 && nx < n && ny > 0 && ny < m && grid[nx][ny])
//                             if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny])
//                             {
//                                 if (grid[nx][ny] == 2)
//                                     hasCity = true;
//                                 node = {nx, ny};
//                                 q.push(node);
//                                 // grid[nx][ny] == 0;
//                                 grid[nx][ny] = 0;
//                             }
//                         }
//                     }
//                     if (hasCity)
//                         cnt++;
//                 }
//             }
//         }
//         return cnt;
//     }
// };


// 法三：DFS
class Solution {
public:
    bool dfs(vector<vector<int>> &grid, int x, int y)
    {
        if (x < 0 || x >= grid.size()) return false;
        if (y < 0 || y >= grid[0].size()) return false;
        if (grid[x][y] == 0) return false;
        bool hasCity = false;
        if (grid[x][y] == 2) 
            hasCity = true;
        grid[x][y] = 0; //重要！
        hasCity = hasCity | dfs(grid, x + 1, y) | dfs(grid, x - 1, y) | dfs(grid, x, y + 1) | dfs(grid, x, y - 1);
        return hasCity;
    }
    int numIslandCities(vector<vector<int>> &grid) {
        if (grid.empty() || grid[0].empty()) {
            return 0;
        }
        int n = grid.size();
        int m = grid[0].size();
        int cnt = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (grid[i][j])
                {
                    if (dfs(grid, i, j))
                        cnt++;
                }
            }
        }
        return cnt;
    }
};